import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 30. 串联所有单词的子串
 */

class Solution3 {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> hashS = new HashMap<>(), hashArr = new HashMap<>();
        int length = words[0].length(), count = 0, n = words.length;
        List<Integer> ret = new LinkedList<>();

        // 统计words数组里每个字符串的个数
        for(int i = 0; i < n; i++) {
            hashArr.put(words[i], hashArr.getOrDefault(words[i], 0) + 1);
        }

        for(int i = 0; i < length; i++) {
            // 需要对hash表里的内容清空
            for(int j = 0; j < n; j++) {
                hashS.put(words[j], 0);
            }
            count = 0; // 清零
            for(int left = i, right = i + length; right <= s.length(); right += length) {
                // 截取当前位置的字符串
                String tmp1 = s.substring(right - length, right);
                // 进窗口
                hashS.put(tmp1, hashS.getOrDefault(tmp1, 0) + 1);

                // 维护count
                if(hashArr.containsKey(tmp1) && hashS.get(tmp1) <= hashArr.get(tmp1)) {
                    count++;
                }

                if(count == n) ret.add(left);

                // 判断
                if(right - left >= n * length) {
                    String tmp2 = s.substring(left, left + length);
                    // 维护count
                    if(hashArr.containsKey(tmp2) && hashS.get(tmp2) <= hashArr.get(tmp2)) {
                        count--;
                    }
                    // 出窗口
                    hashS.put(tmp2, hashS.get(tmp2) - 1);
                    left += length;
                }
            }
        }

        return ret;
    }
}